005.Longest Palindromic [M]

题目

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路

可以用的算法有改良KMP还有manacher（马拉车）算法，毫无疑问，manacher算法是专门用来解决最长子串问题的，也是最简便的。关于这个算法可以看: Manacher算法

  1. class Solution { 
  2.     public: 
  3.         string longestPalindrome(string s) { 
  4.             //manacher 
  5.             int bound = 0; 
  6.             int id,max_pos=0; 
  7.             int new_len = 2*s.length()+2; 
  8.             vector<int> P(new_len,1); 
  9.             string new_str(new_len-1,'#'); 
  10.             //生成新串，把所有的字符串通过’#’扩展成奇数 
  11.             for(int i = 0;i < s.length();i++) 
  12.             { 
  13.                 new_str[2*i+1] = s[i]; 
  14.             } 
  15.             new_str = '$'+new_str +='\0'; //防止越界 
  16.             //manacher算法 
  17.             for(int i=1;i < new_len; i++) 
  18.             {
  19.                 if(i < bound) 
  20.                 { 
  21.                     P[i] = min(bound-i,P[2*id-i]); //如果在范围内，找对称面的P[id-(i-id)]和max_pos-i的最小值 
  22.                 } 
  23.                  while(new_str[i-P[i]] == new_str[i+P[i]])//查找以这个字符为中心的回文串 
  24.                     { 
  25.                         P[i]++; 
  26.                     } 
  27.                     //更新id和bound 
  28.                     if(i+P[i] > bound) 
  29.                     { 
  30.                         bound = i+P[i]; 
  31.                         id = i; 
  32.                     } 
  34.                 max_pos = P[i] > P[max_pos]?i:max_pos; 
  35.             } 
  36.             int len = P[max_pos]-1; 
  37.             int start = (max_pos-P[max_pos])/2;
  38.             return s.substr(start,len);
  39.         }
  40. };